/**
    算法描述：
    核心问题：
    解决所需数据结构+算法：
**/
#include<bits/stdc++.h> 
using namespace std;
 
struct edge{
    int x, y, c, pre;
}a[400020];
int alen = 0, last[10010] = {0};
 
void ins(int x, int y, int c) {
    a[++alen] = edge{x, y, c, last[x]};
    last[x] = alen;
}
 
int n, m;
bool v[10010] = {false};
int d[10010] = {0};
 
void dfs(int x) {
    for (int k=last[x]; k; k=a[k].pre) {
        int y = a[k].y;
        if (v[y])
            continue;
        if (d[y] > d[x]+a[k].c) {
            d[y] = d[x]+a[k].c;
            if(!v[y]) {
                v[y] = true;
                dfs(y);
                v[y] = false;
            }
        }
    }
}
 
int main() {
    scanf("%d%d", &n, &m);
    while(m--)  {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        ins(x, y, c);
        ins(y, x, c);
    }
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;
    dfs(1);
    d[n] == d[0] ? printf("-1") : printf("%d", d[n]);
    return 0;
}